/*
 * @lc app=leetcode.cn id=120 lang=typescript
 *
 * [120] 三角形最小路径和
 */

// @lc code=start
function minimumTotal(triangle: number[][]): number {
  const m = triangle.length;
  // 滚动数组
  const dp = new Array(2).fill(0).map((_) => new Array(m));
  // 初始化
  dp[(m - 1) % 2] = [...triangle[m - 1]];

  for (let i = m - 2; i >= 0; i--) {
    const currIdx = i % 2;
    const nextIdx = Number(!currIdx);
    for (let j = 0; j <= i; j++) {
      // 当前值加上下一层的相邻节点的最小值
      dp[currIdx][j] = triangle[i][j] + Math.min(dp[nextIdx][j], dp[nextIdx][j + 1]);
    }
  }

  return dp[0][0];
}
// @lc code=end
